package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.ArrUtils;
import com.chenxys.algorithm.common.IntegerUtils;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150">删除有序数组中的重复项</a><br/>
 *      　　给你一个 {@code 非严格递增排列}的数组nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回nums中唯一元素的个数。<br/>
 *      1 <= nums.length <= 3 * 10^4<br/>
 *      -10^4 <= nums[i] <= 10^4<br/>
 *      nums 已按 非严格递增 排列<br/>
 *      例: <br/>
 *          输入: nums = [1,1,2]<br/>
 *          输出: 2, nums = [1,2,_]<br/>
 *          解释: 函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。<br/>
 * </p>
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/22 16:01
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode26 {

    /**
     * <p>
     *     删除有序数组中的重复项
     * </p>
     */
    public static  int removeDuplicates(int[] nums) {
        int N = nums.length;
        if(nums == null || N == 0) return 0;
        int index = 0;
        for (int i = 0; i < N; i++) {
            if (nums[i] == nums[index]) {
                continue;
            }
            nums[index + 1] = nums[i];
            index++;
        }
        return ++index;
    }


    /**
     * <p>
     *     删除有序数组中的重复项
     * </p>
     */
    public static int checkRemoveDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int p = 0;
        int q = 1;
        while(q < nums.length){
            if(nums[p] != nums[q]){
                nums[p + 1] = nums[q];
                p++;
            }
            q++;
        }
        return p + 1;
    }

    public static void main(String[] args) {
        int maxSize = 100;
        int maxVal = 100;
        int testTimes = 10000;
        System.out.println("Test Start!");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = ArrUtils.generateSortRandomArr(maxSize, maxVal);
            int[] copyArr = ArrUtils.copyArr(arr);
            int[] oriArr = ArrUtils.copyArr(arr);
            if (removeDuplicates(arr) != checkRemoveDuplicates(copyArr)) {
                System.out.println("Oops!");
                ArrUtils.printArr(oriArr);
                break;
            }
        }
        System.out.println("Test End!");
    }
}
